Embodiments relate to relational models of knowledge, such as a graph-based data store, can be used to provide answers to search queries. Such models describe real-world entities (people, places, things) as facts in the form of graph nodes and edges between the nodes. While such graphs may represent a significant amount of facts, even the largest graphs may be missing tens of millions of facts, or may have incorrect facts. For example, relationships, edges or other attributes between two or more nodes can often be missing.